/**
 * 2
 *  
 * @Author : Ruoyu Wang
 * @DateTime : 24-9-14 下午2:26
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     *
     * 计算摆动序列的最长子序列的长度
     * @param nums int整型 vector 摆动序列
     * @return int整型
     */
    int wiggleMaxLength(vector<int> &nums) {
        int f[nums.size() + 1][2];
        f[0][0] = 0;
        f[0][1] = 0;
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            f[i + 1][0] = 1;
            f[i + 1][1] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    f[i + 1][0] = max(f[i + 1][0], f[j + 1][1] + 1);
                } else if (nums[i] < nums[j]) {
                    f[i + 1][1] = max(f[i + 1][1], f[j + 1][0] + 1);
                }
            }
            res = max(res, f[i + 1][0]);
            res = max(res, f[i + 1][1]);
        }
        return res;
    }
};

int main() {
    Solution sl;
    vector<int> nums = {1, 7, 4, 9, 2, 5};
    cout << sl.wiggleMaxLength(nums);
    return 0;
}